A graph is an abstract data type, in which vertices typically represent objects or entities, and edges represent relationships or connections between the objects or entities. Graph structures are used in multiple computerized applications and environments.
A recognized issue in environments having a graph representation relates to change notification, i.e., how to propagate changes made to one node within the graph, so that integrity and consistency of the graph and its data is preserved, while avoiding resource waste, including memory, time, communication volume, processing power and others.
One common usage of graph representation relates to a computerized environment comprising multiple computers (also referred to as machines or nodes) which may be arranged in clusters. One or more of the nodes executes one or more applications which use multiple components, such as web pages, units, executables, static libraries, dynamic libraries, or the like. For example, an enterprise portal may be installed on a cluster of nodes comprising a multiplicity of computers. Each of the enterprise-portal components, which reside on the various computers in the cluster, may depend on multiple other components and load them into memory during execution, into for example a cache memory used for efficient access to the components. When using a graph representation, the loaded or executed components are the vertices, and dependency between two components is represented as an edge.
When any of the components changes, for example by an application executed on another node in the cluster, the component as well as other components dependent on it may have to be updated as well, depending on the dependency, and the type of change. Since components may also be removed from the cache memory, a situation may occur in which a component does not exist in memory, but still has to be updated so that other components dependent on it can be updated. As an enterprise portal may contain tens, hundreds or thousands of components, the decisions of whether and which components should be held in memory, and which change notification policy is used, have heavy implications on the resource consumption and the performance of the computing platform and the executed applications.
One common solution is keeping all components required for an application in the memory device of a computing platform at all times, and receiving specific notification for each updated component. This solution provides for time-efficient updating, but wastes a lot of memory by keeping components which may be unnecessary in the memory.
Another solution involves keeping in memory only the necessary components, and evacuating other components that are used, for example, during loading of other components but are not required at a later time, and receiving notification for components that have been changed directly. In such case, the computing platform has to determine which other components should be updated. This solution requires higher management effort on the side of the application, and is thus wasteful in time and processing power resources.
There is thus a need in the art for a method and apparatus for maintaining and propagating change notifications within computerized graph-structured systems, while making efficient usage of memory, time, CPU and other resources.